home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / SET.H < prev    next >
C/C++ Source or Header  |  1992-11-29  |  19KB  |  437 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/05/89 -- Initial design and implementation
  13. // Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
  14. // Updated: MBN 09/15/89 -- Added conditional exception handling
  15. // Updated: MBN 10/03/89 -- Fixed put() method to update value
  16. // Updated: MBN 10/07/89 -- Fixed double entry count with use of iterators
  17. // Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and changed
  18. //                          state from bit set to bit set/get macros
  19. // Updated: LGO 10/19/89 -- Fixed operator==() for tables with different bucket
  20. //                          count but same elements -- tables grew separately
  21. // Updated: MBN 12/22/89 -- Sprinkled "const" qualifiers all over the place!
  22. // Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
  23. // Updated: MBN 02/23/90 -- Made operators -=, ^=, |=, &= return reference 
  24. // Updated: MJF 03/12/90 -- Added group names to RAISE
  25. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  26. // Updated: VDN 02/21/92 -- New lite version
  27. // Updated: JAM 09/24/92 -- removed DOS specifics, stdized #includes
  28. // Updated: JAM 09/24/92 -- modernize template syntax, remove macro hacks
  29. // Updated: JAM 09/24/92 -- made *_state typedef a nested typedef "IterState"
  30. //                          as per new Iterator convention
  31. //
  32. // The Set<Type> class implements a set  of elements  of a user-specified type.
  33. // This is accompilshed by using the parameterized type capability of C++.  The
  34. // Set<Type> class implements a simple one-element hash table where the key and
  35. // the value are the same thing.  The type of the Set class is the key/value in
  36. // the Hash Table.  The  Set<Type> class is  derived from the Hash_Table  class
  37. // and is  dynamic  in nature.  It's size   (ie. the number of  buckets  in the
  38. // table) is  always some prime number. Each  bucket holds 8 items.   No wholes
  39. // are left in a bucket; if a key/value is removed from the middle of a bucket,
  40. // following entries are moved up.   When a hash on a  key ends  up in a bucket
  41. // that is full, the table is enlarged.
  42. //
  43. // The private data  section of  a Set<Type> has  a  slot that   points  to the
  44. // physical memory allocated for some prime number of buckets each of which has
  45. // memory allocated for 8 items.  The number of buckets  currently in the table
  46. // is accessed by an index into a static table of  selected prime numbers. This
  47. // static table contained within  the class eliminates  the somewhat  expensive
  48. // runtime computation of prime numbers.  The  table consists of  prime numbers
  49. // where the difference  between  any two successive entries gets progressively
  50. // larger as you move through the table.  The specified range of primes results
  51. // in an arbitrary limitation of 2^22 entries in a single hash table.
  52. //
  53. // When a hash on a key ends up in a bucket that is full, the table is enlarged
  54. // to the next prime number of buckets or to the prime number  that is at least
  55. // large enough to accommodate  a user-specified growth  ratio. The  entries in
  56. // the  buckets are then  rehashed   into the   new  table.  Selection  of   an
  57. // appropriate hash function  is  crucial to  uniform  distribution through the
  58. // table. The default   hash  utilizes  the number   of  buckets  in order   to
  59. // accomplish this. A user-supplied function should do something similar.
  60. //
  61. // Other items in the private data section include a pointer to a hash function
  62. // and a  pointer to  a compare  function.   The compare   function  is used in
  63. // equality operations on key/value items.  The default compare function is the
  64. // built-in == operator.  The default  hash function is either a  simple 32 bit
  65. // value if sizeof(Type) is 4, that is shifted left  three bits with the result
  66. // modulo the number of buckets determining the  hash. This  is ideal when Type
  67. // is a pointer..   If sizeof(Type) is greater than  4,  then the 32 bit  value
  68. // used  is  the  result of  exclusive-oring  successive 32-bit values  for the
  69. // length of T1, and then applying the same  bit shift  and modulo operation as
  70. // before.
  71. //
  72. // Three different constructors are provided.  The  first  constructor takes no
  73. // arguments and creates  a  Set that can  contain 24 items before  resizing is
  74. // necessary.  The second constructor accepts an integer argument and creates a
  75. // Set that  can accomodate at  least the specified number  of items.  Finally,
  76. // the third constructor takes a single argument  consisting of a  reference to
  77. // another Set and duplicates its size and contents.
  78. //
  79. // Methods are provided to put, query,  and remove  an item from a set, perform
  80. // the  intersection, union,  difference, and exclusive-or  of two  sets, check
  81. // equality and inequality of  two set  objects, and determine if  one set is a
  82. // subset of another. In  addition, the notion of  a current position  within a
  83. // set is maintained and reset, next, previous,  find,  and get value functions
  84. // for setting and using the current position are provided.  Also  for use with
  85. // the current position are the next  union, next intersetion, next difference,
  86. // and next  exclusive-or  operations. These    allow a   user to access    the
  87. // first/next individual item that results  from some logical  operation. These
  88. // functions are particularly efficient, since no temporary Set<Type> structure
  89. // is created. Finally, functions to set the  compare and hash functions for an
  90. // instance of a set, get the count of the number of items in a set, output the
  91. // set to a stream, clear all elements from a set,  and determine if  a  set is
  92. // empty are also available.
  93. //
  94. // Use envelope to avoid deep copy and mutate in place.
  95.  
  96. #ifndef SETH                    // If no Set class,
  97. #define SETH                    // define it
  98.  
  99. #ifndef BASE_HASH_TABLEH            // If no Base Hash class
  100. #include <cool/Base_Hash.h>            // define it
  101. #endif
  102.  
  103. #include <cool/String.h>   //## only because of hack()
  104.  
  105. //## hack to workaround BC++ 3.1 Envelope bug
  106. #undef CoolEnvelope_H
  107. #define CoolEnvelope CoolEnvelope_Set
  108.  
  109. template<class CoolLetter> class CoolEnvelope;
  110.  
  111. template <class Type>
  112. class CoolSet : public CoolBase_Hash_Table {    // Define CoolSet
  113. public:
  114.   typedef long IterState;            // Current position state
  115.   typedef Boolean (*Compare) (const Type&, const Type&);
  116.   typedef long (*Hash) (const Type&);
  117.  
  118.   CoolSet();                // Set of default size
  119.   CoolSet(unsigned long);        // Set for at least size
  120.   CoolSet(const CoolSet<Type>&);        // Set with reference
  121.   ~CoolSet();                // Destructor
  122.  
  123.   CoolSet<Type>& operator= (const CoolSet<Type>&); // Assignment
  124.   inline CoolSet<Type>& operator= (CoolEnvelope< CoolSet<Type> >&); // Envelope back to set
  125.   
  126.   Boolean find (const Type&);            // Set current position
  127.   Type& value ();                // Get value at current
  128.   Boolean remove ();                // Remove item current position
  129.   
  130.   Boolean put (const Type&);            // Put element into set
  131.   Boolean remove (const Type&);            // Remove element from set
  132.   Boolean search (CoolSet<Type>&);        // Subset operator
  133.   Boolean resize (long);            // Resize for at least count
  134.   
  135.   CoolSet<Type>& operator|= (const CoolSet<Type>&);    // Union of two sets
  136.   CoolSet<Type>& operator-= (const CoolSet<Type>&);    // Difference of two sets
  137.   CoolSet<Type>& operator^= (const CoolSet<Type>&);    // Exclusive-or of two sets
  138.   CoolSet<Type>& operator&= (const CoolSet<Type>&);    // Intersection of two sets
  139.  
  140. //   Use envelope to avoid deep copy on return by value, and mutate in place
  141. //   inline friend CoolSet<Type> operator| (const CoolSet<Type>&,const CoolSet<Type>&);
  142. //   inline friend CoolSet<Type> operator- (const CoolSet<Type>&,const CoolSet<Type>&);
  143. //   inline friend CoolSet<Type> operator^ (const CoolSet<Type>&,const CoolSet<Type>&);
  144. //   inline friend CoolSet<Type> operator& (const CoolSet<Type>&,const CoolSet<Type>&);
  145.   
  146.   inline void set_union (const CoolSet<Type>&);    // Union of two sets       
  147.   inline void set_difference (const CoolSet<Type>&); // Difference of two sets  
  148.   inline void set_xor (const CoolSet<Type>&);         // Exclusive-or of two sets
  149.   inline void set_intersection (const CoolSet<Type>&); // Intersection of two sets
  150.   
  151.   Boolean next_union (CoolSet<Type>&);        // Return next union item
  152.   Boolean next_difference (CoolSet<Type>&);    // Return next difference item
  153.   Boolean next_xor (CoolSet<Type>&);        // Return next exclusive-or
  154.   Boolean next_intersection (CoolSet<Type>&);    // Return next intersection
  155.   
  156.   friend ostream& operator<< (ostream&, const CoolSet<Type>&); // Overload output
  157.   /*inline##*/ friend ostream& operator<< (ostream&, const CoolSet<Type>*); 
  158.  
  159.   Boolean operator== (const CoolSet<Type>&) const; // Set equality test
  160.   inline Boolean operator!= (const CoolSet<Type>&) const; // Set inequality test
  161.   
  162.   inline void set_hash (Hash);    // Set the hash function
  163.   void set_compare (Compare = NULL); // Set compare function
  164.  
  165. private:
  166.   Type next_data;                // Slot to hold next_union data
  167.  
  168.   struct Bucket {            // Structure for bucket
  169.     Type data[BUCKET_SIZE];
  170.   };
  171.  
  172.   Bucket* table;                // Pointer to key buckets
  173.   Hash h_function;        // Pointer to hash function
  174.   Compare compare;        // Pointer operator== function
  175.   friend Boolean CoolSet_are_keys_equal (const Type&, const Type&);
  176.   friend long CoolSet_default_hash (const Type&);
  177.   
  178.   Boolean do_find (const Type&) const;        // CoolSet current position
  179. };
  180.  
  181. //## BC++ 3.1 bug
  182. void hack(CoolSet<int>);
  183. void hack(CoolSet<double>);
  184. void hack(CoolSet<char*>);
  185. void hack(CoolSet<CoolString>);
  186. #include <cool/Gen_String.h>
  187. void hack(CoolSet<CoolGen_String>);
  188.  
  189. //## add your type above
  190. #include <cool/Envelope.h>    //## BC++ 3.1 bug prevents from moving to top
  191.  
  192. // Use envelope to avoid deep copy on return by value, and mutate in place
  193. template<class Type>
  194. inline CoolEnvelope< CoolSet<Type> > operator| (const CoolSet<Type>&arg1,const CoolSet<Type>&arg2)
  195.    { return CoolEnvOp(vertical)(arg1, arg2); }
  196. template<class Type>
  197. inline CoolEnvelope< CoolSet<Type> > operator- (const CoolSet<Type>&arg1,const CoolSet<Type>&arg2)
  198.    { return CoolEnvOp(minus)(arg1, arg2); }
  199. template<class Type>
  200. inline CoolEnvelope< CoolSet<Type> > operator^ (const CoolSet<Type>&arg1,const CoolSet<Type>&arg2)
  201.    { return CoolEnvOp(caret)(arg1, arg2); }
  202. template<class Type>
  203. inline CoolEnvelope< CoolSet<Type> > operator& (const CoolSet<Type>&arg1,const CoolSet<Type>&arg2)
  204.    { return CoolEnvOp(ampersand)(arg1, arg2); }
  205.  
  206. // operator=  -- Assignment from an envelope back to real set
  207. // Input:     envelope reference
  208. // Output:    Set reference with contents in envelope being swapped over
  209.  
  210. template<class Type>
  211. inline CoolSet<Type>& CoolSet<Type>::operator= (CoolEnvelope< CoolSet<Type> >& env){
  212.   env.shallow_swap((CoolEnvelope< CoolSet<Type> >*)this, &env); // same physical layout
  213.   return *this;
  214. }
  215.  
  216.  
  217. // set_union -- Determine the union of two sets
  218. // Input:       Reference to a Bit Set object
  219. // Output:      None
  220.  
  221. template <class Type> 
  222. inline void CoolSet<Type>::set_union (const CoolSet<Type>& b) {
  223.   this->operator|= (b);
  224. }
  225.  
  226.  
  227. // set_difference -- Determine the difference of two sets
  228. // Input:            Reference to a Bit Set object
  229. // Output:           None
  230.  
  231. template <class Type> 
  232. inline void CoolSet<Type>::set_difference (const CoolSet<Type>& b) {
  233.   this->operator-= (b);
  234. }
  235.  
  236.  
  237. // set_xor -- Determine the exclusive-OR of two sets
  238. // Input:     Reference to a Bit Set object
  239. // Output:    None
  240.  
  241. template <class Type> 
  242. inline void CoolSet<Type>::set_xor (const CoolSet<Type>& b) {
  243.   this->operator^= (b);
  244. }
  245.  
  246.  
  247. // set_intersection -- Determine the intersection of two sets
  248. // Input:              Reference to a Bit Set object
  249. // Output:             None
  250.  
  251. template <class Type> 
  252. inline void CoolSet<Type>::set_intersection (const CoolSet<Type>& b) {
  253.   this->operator&= (b);
  254. }
  255.  
  256.   
  257. // operator!= -- Return logical result of not equal comparison test
  258. // Input:        Reference to another Bit Set object
  259. // Output:       Boolean TRUE/FALSE
  260.  
  261. template <class Type> 
  262. inline Boolean CoolSet<Type>::operator!= (const CoolSet<Type>& b) const {
  263.   return (!(this->operator== (b)));
  264. }
  265.  
  266.  
  267. // Set_hash -- Set the hash function for this instance
  268. // Input:      Pointer to hash function
  269. // Output:     None
  270.  
  271. template <class Type> 
  272. inline void CoolSet<Type>::set_hash (long (*h) (const Type&)) {
  273.   this->h_function = h;
  274. }
  275.  
  276.  
  277. // 
  278. // // operator| -- Return the union of two sets, that is all elements in each set
  279. // // Input:       Reference to a set
  280. // // Output:      New Set object containing union of two sets
  281. // 
  282. // template <class Type> CoolSet {
  283. // inline CoolSet<Type> operator| (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  284. //   CoolSet<Type> result(s1);            // Temporary variable
  285. //   result.operator|=(s2);            // Mutate temp with union
  286. //   return result;                // Return resulting union
  287. // }}
  288. // 
  289. // 
  290. // // operator- -- Return the difference of two sets, that is all elements in
  291. // //              the first set that are not in the second
  292. // // Input:       Reference to a set
  293. // // Output:      New CoolSet object containing difference of two sets
  294. // 
  295. // template <class Type> CoolSet{
  296. // inline CoolSet<Type> operator- (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  297. //   CoolSet<Type> result(s1);            // Temporary variable
  298. //   result.operator-=(s2);            // Mutate temp with difference
  299. //   return result;                // Return resulting union
  300. // }}
  301. // 
  302. // 
  303. // // operator^ -- Return the exclusive-OR of two sets, that is all elements in
  304. // //              the first set that are not in the second and all elements in the
  305. // //              second set that are not in the first
  306. // // Input:       Reference to set
  307. // // Output:      New CoolSet object containing XOR of two sets
  308. // 
  309. // template <class Type> CoolSet {
  310. // inline CoolSet<Type> operator^ (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  311. //   CoolSet<Type> result(s1);            // Temporary variable
  312. //   result.operator^=(s2);            // Mutate temp with xor
  313. //   return result;                // Return resulting xor
  314. // }}
  315. // 
  316. // 
  317. // // operator& -- Return the intersection of two sets, that is all elements that
  318. // //              are in both sets
  319. // // Input:       Reference to CoolSet object
  320. // // Output:      New CoolSet object containing intersection of two sets
  321. // 
  322. // template <class Type> CoolSet {
  323. // inline CoolSet<Type> operator& (const CoolSet<Type>& s1, const CoolSet<Type>& s2) {
  324. //   CoolSet<Type> result(s1);            // Temporary variable
  325. //   result.operator&=(s2);            // Mutate with intersection
  326. //   return result;                // Return resulting intersection
  327. // }}
  328.  
  329.  
  330. // next_intersection -- Position at the next intersection of two Sets.
  331. // Input:               Reference to CoolSet object
  332. // Output:              TRUE/FALSE, current position updated
  333.  
  334. template <class Type> 
  335. Boolean CoolSet<Type>::next_intersection (CoolSet<Type>& s) {
  336.   if (this->curpos != INVALID && TRAVERSED(this->curpos)) // Traversed already?
  337.     return FALSE;                // Indicate no more elements
  338.   while (this->next () == TRUE)    {        // While there are elements
  339.     if (BUCKET_NUMBER(this->curpos) >= s.get_bucket_count())
  340.       return FALSE;                // Return failure status
  341.     if (s.find(this->value()) == TRUE)        // If element in 2nd set
  342.       return TRUE;                // Return success status
  343.   }
  344.   this->curpos = INVALID;            // Invalidate current position
  345.   return FALSE;                    // Return failure status
  346. }
  347.  
  348.  
  349. // next_union -- Position at the next union of two Sets.
  350. // Input:        Reference to CoolSet object
  351. // Output:       TRUE/FALSE, current position updated
  352.  
  353. template <class Type> 
  354. Boolean CoolSet<Type>::next_union (CoolSet<Type>& s) {
  355.   if ((this->curpos != INVALID && !TRAVERSED(this->curpos)) ||
  356.       this->curpos == INVALID) {
  357.     if (this->next () == TRUE)            // If more elements in 1st set
  358.       return TRUE;                // Return success status
  359.     else                    // Else set traversed flag
  360.       this->curpos = SET_TRAVERSED(TRUE);
  361.   }
  362.   while (s.next () == TRUE) {            // While more elements in 2nd 
  363.     if (this->find(s.value()) == FALSE) {    // If element not in 1st set
  364.       this->curpos |= SET_TRAVERSED(TRUE);    // Reset flag zeroed by find
  365.       this->next_data = s.value();        // Refer to next piece of data
  366.       return TRUE;                // Return success status
  367.     }
  368.   }
  369.   this->curpos = INVALID;            // Invalidate current position
  370.   return FALSE;                    // Return failure status
  371. }
  372.  
  373.  
  374. // next_difference -- Position at the zero-relative integer of the next bit in 
  375. //                    the difference of two CoolSets.
  376. // Input:             Reference to CoolSet object
  377. // Output:            TRUE/FALSE, current position updated
  378.  
  379. template <class Type> 
  380. Boolean CoolSet<Type>::next_difference (CoolSet<Type>& s) {
  381.   if (this->curpos != INVALID && TRAVERSED(this->curpos)) // Traversed already?
  382.     return FALSE;                // Indicate no more elements
  383.   while (this->next () == TRUE)    {        // While there are elements
  384.     if (BUCKET_NUMBER(this->curpos) >= s.get_bucket_count())
  385.       return FALSE;                // Return failure status
  386.     if (s.find(this->value()) == FALSE)        // If element not in 2nd set
  387.       return TRUE;                // Return success status
  388.   }
  389.   this->curpos = INVALID;            // Invalidate current position
  390.   return FALSE;                    // Return failure status
  391. }
  392.  
  393.  
  394. // next_xor -- Position at the zero-relative integer of the next bit in 
  395. //             the XOR of two Sets.
  396. // Input:      Reference to CoolSet object
  397. // Output:     TRUE/FALSE, current position updated
  398.  
  399. template <class Type> 
  400. Boolean CoolSet<Type>::next_xor (CoolSet<Type>& s) {
  401.   if ((this->curpos != INVALID && !TRAVERSED(this->curpos)) ||
  402.       this->curpos == INVALID) {
  403.     if (this->next_difference (s) == TRUE)    // If more elements in 1st set
  404.       return TRUE;                // Return success status
  405.     else {                    // Else set traversed flag
  406.       this->curpos = SET_TRAVERSED(TRUE);
  407.       s.reset();                // Reset current position
  408.     }
  409.       }
  410.   if ((s.curpos != INVALID && !TRAVERSED(s.curpos)) || s.curpos == INVALID) {
  411.     this->reset();                // Reset 1st set pointer
  412.     if (s.next_difference (*this)) {        // If any other elements in 2nd
  413.       this->curpos |= SET_TRAVERSED(TRUE);    // Reset flag set by find
  414.       this->next_data = s.value();        // Save data for value()
  415.       return TRUE;                // Return success status
  416.     }
  417.   }
  418.   this->curpos = INVALID;            // Invalidate current position
  419.   return FALSE;                    // Return failure status
  420. }
  421.  
  422.  
  423. // operator<< -- Overload the output operator to provide a crude print
  424. //               capability for CoolSet objects
  425. // Input:        ostream reference, CoolSet pointer
  426. // Output:       None
  427.  
  428. template <class Type>
  429. inline ostream& operator<< (ostream& os, const CoolSet<Type>* s) {
  430.   return operator<< (os, *s);
  431. }
  432.  
  433. //## hack to workaround BC++ 3.1 Envelope bug
  434. #undef CoolEnvelope
  435.  
  436. #endif                        // End of SETH
  437.